package com.jichangxiu.flow.server.core.utils;

import cn.hutool.core.util.ObjectUtil;
import cn.hutool.core.util.StrUtil;
import com.jichangxiu.flow.server.core.context.LiteFlowContext;
import com.jichangxiu.flow.server.core.entity.Bo.EdgeBo;
import com.jichangxiu.flow.server.core.entity.Bo.NodeBo;
import com.jichangxiu.flow.server.core.entity.Bo.ProcessBo;
import com.jichangxiu.flow.server.core.entity.dto.Edge;
import com.jichangxiu.flow.server.core.entity.dto.Node;
import com.jichangxiu.flow.server.core.enums.CategoryEnums;
import com.jichangxiu.flow.server.core.enums.NodeEnums;
import com.jichangxiu.flow.server.core.enums.ProcessEnums;

import java.math.BigDecimal;
import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * TreeUtils:
 *
 * @author Jcx
 * @create 2025-01-01 00:00:00
 */
public class TreeUtils {

    /**
     * 根据 id 查找节点
     *
     * @param root     根节点
     * @param targetId 目标节点ID
     * @return 目标节点
     */
    public static NodeBo findNodeBoById(NodeBo root, String targetId) {
        if (root == null || targetId == null) {
            return null;
        }
        if (targetId.equals(root.getId())) {
            return root;
        }
        if (root.getChildNodeBoList() != null) {
            for (NodeBo child : root.getChildNodeBoList()) {
                NodeBo result = findNodeBoById(child, targetId);
                if (result != null) {
                    return result;
                }
            }
        }
        return null;
    }

    /**
     * 获取所有子节点数量
     *
     * @param nodeBo 逻辑子流程节点
     * @return 所有子节点数量
     */
    public static BigDecimal getAllChildNodeBoCount(NodeBo nodeBo, Boolean ignoreMark) {
        // 初始化
        BigDecimal size = BigDecimal.ZERO;
        // 本节点不为空 加一
        if (ignoreMark) {
            if (ObjectUtil.isNotEmpty(nodeBo) && !CategoryEnums.MARK.name().equals(nodeBo.getCategory())) {
                size = size.add(BigDecimal.ONE);
            }
        } else {
            if (ObjectUtil.isNotEmpty(nodeBo)) {
                size = size.add(BigDecimal.ONE);
            }
        }
        // 没有子节点
        if (ObjectUtil.isEmpty(nodeBo.getChildNodeBoList())) {
            return size;
        }
        // 循环子节点
        for (NodeBo subNodeBo : nodeBo.getChildNodeBoList()) {
            BigDecimal subSize = getAllChildNodeBoCount(subNodeBo, ignoreMark);
            size = size.add(subSize);
        }
        return size;
    }

    /**
     * 填充循环节点的父节点 id
     *
     * @param nodeBoList 节点列表
     */
    public static void setNodeBoCycleParentId(List<NodeBo> nodeBoList) {
        if (nodeBoList == null || nodeBoList.isEmpty()) return;
        // 构建 id -> Node 的映射，方便快速查找
        Map<String, NodeBo> idByNodeToMap = nodeBoList.stream().collect(Collectors.toMap(NodeBo::getId, node -> node));
        // 递归设置 parentId
        for (NodeBo nodeBo : nodeBoList) {
            recursionSetNodeBoCycleParentId(nodeBo, idByNodeToMap);
        }
    }

    /**
     * 递归设置节点的父节点 id
     *
     * @param parentNodeBo  父节点
     * @param idByNodeToMap 节点关系映射
     */
    private static void recursionSetNodeBoCycleParentId(NodeBo parentNodeBo, Map<String, NodeBo> idByNodeToMap) {
        if (parentNodeBo.getChildren() == null || parentNodeBo.getChildren().isEmpty()) return;
        for (String childId : parentNodeBo.getChildren()) {
            NodeBo childNodeBo = idByNodeToMap.get(childId);
            if (childNodeBo != null) {
                childNodeBo.setCycleParentId(parentNodeBo.getId());
                // 继续递归处理子节点
                recursionSetNodeBoCycleParentId(childNodeBo, idByNodeToMap);
            }
        }
    }

    /**
     * 递归设置节点的父节点 id
     *
     * @param parentNodeBo 父节点
     */
    public static void setNodeBoParentId(NodeBo parentNodeBo) {
        if (parentNodeBo.getChildNodeBoList() == null || parentNodeBo.getChildNodeBoList().isEmpty()) return;
        for (NodeBo childNodeBo : parentNodeBo.getChildNodeBoList()) {
            if (childNodeBo != null) {
                childNodeBo.setParentId(parentNodeBo.getId());
                // 继续递归处理子节点
                setNodeBoParentId(childNodeBo);
            }
        }
    }

    /**
     * 构建 NodeBo 节点树
     *
     * @param liteFlowContext 逻辑流程上下文
     * @return 业务节点对象
     */
    public static NodeBo buildNodeBoTree(LiteFlowContext liteFlowContext, boolean isMainProcess) {
        // 获取根节点 id
        String rootNodeId = isMainProcess ? getMainProcessRootNodeId(liteFlowContext.getNodeBoList(), liteFlowContext.getEdgeBoList())
                : getSubProcessRootNodeId(liteFlowContext.getNodeBoList(), liteFlowContext.getEdgeBoList());
        if (rootNodeId == null) throw new RuntimeException("未获取到有效根节点");
        // 根节点
        NodeBo rootNodeBo = liteFlowContext.getIdByNodeBoToMap().get(rootNodeId);
        if (rootNodeBo == null) throw new RuntimeException("未获取到有效根节点");
        NodeBo newRootNodeBo = ObjectUtil.cloneByStream(rootNodeBo);
        if (!(CategoryEnums.WHILE.name().equals(rootNodeBo.getCategory())
                || CategoryEnums.ITERATOR.name().equals(rootNodeBo.getCategory())
                || CategoryEnums.FOR.name().equals(rootNodeBo.getCategory()))
                && ObjectUtil.isEmpty(liteFlowContext.getSourceIdByEdgeBoListToMap().get(rootNodeId))) {
            // 不是循环节点
            // 根节点没有出边，则代表流程图只有一个节点，即根节点
            return newRootNodeBo;
        }
        // 递归构建节点树
        newRootNodeBo.setChildNodeBoList(recursionBuildNodeBoTree(liteFlowContext, rootNodeId));
        return newRootNodeBo;
    }

    /**
     * 递归构建节点树
     *
     * @param liteFlowContext 逻辑流程上下文
     * @param nodeId          当前节点id
     * @return 业务节点对象集合
     */
    private static List<NodeBo> recursionBuildNodeBoTree(LiteFlowContext liteFlowContext, String nodeId) {
        List<NodeBo> nodeBoList = new ArrayList<>();
        // 获取当前节点
        NodeBo nodeBo = liteFlowContext.getIdByNodeBoToMap().get(nodeId);
        if (NodeEnums.ForNode.name().equals(nodeBo.getType()) || NodeEnums.WhileNode.name().equals(nodeBo.getType()) || NodeEnums.IteratorNode.name().equals(nodeBo.getType())) {
            // 循环组件，当中的流程是一个子流程
            List<String> childNodeIdList = nodeBo.getChildren();
            if (ObjectUtil.isEmpty(childNodeIdList)) return nodeBoList;
            // 子流程所有节点
            List<Node> subNodeList = getSubProcessNodeList(childNodeIdList, liteFlowContext);
            // 子流程所有边
            List<Edge> subEdgeList = getSubProcessEdgeList(childNodeIdList, liteFlowContext);
            // 构建子流程上下文
            LiteFlowContext subLiteFlowContext = LiteFlowContext.buildLogicFlowContext(nodeId, subNodeList, subEdgeList);
            // 构建子流程业务节点
            nodeBoList.add(buildNodeBoTree(subLiteFlowContext, false));
        } else {
            // 非循环组件
            // 当前节点的所有出边
            List<EdgeBo> sourceEdgeBoList = liteFlowContext.getSourceIdByEdgeBoListToMap().get(nodeId);
            if (ObjectUtil.isEmpty(sourceEdgeBoList)) return nodeBoList;
            for (EdgeBo sourceEdge : sourceEdgeBoList) {
                // 出边没有到达节点ID，则代表该出边没有到达节点，则跳过该出边
                String targetSubNodeId = sourceEdge.getTargetNodeId();
                if (StrUtil.isEmpty(targetSubNodeId)) continue;
                // 根据该出边到达的子节点ID获取子节点
                NodeBo subNodeBo = liteFlowContext.getIdByNodeBoToMap().get(targetSubNodeId);
                // 子节点不存在，则跳过该子节点
                if (ObjectUtil.isEmpty(subNodeBo)) continue;
                NodeBo newSubNodeBo = ObjectUtil.clone(subNodeBo);
                // 递归构建子节点树
                newSubNodeBo.setChildNodeBoList(recursionBuildNodeBoTree(liteFlowContext, targetSubNodeId));
                // 添加子节点
                nodeBoList.add(newSubNodeBo);
            }
        }
        return nodeBoList;
    }

    /**
     * 获取根节点 id
     *
     * @param nodeBoList 节点列表
     * @param edgeBoList 边列表
     * @return 根节点 id
     */
    private static String getMainProcessRootNodeId(List<NodeBo> nodeBoList, List<EdgeBo> edgeBoList) {
        Map<String, NodeBo> idByNodeBoToMap = nodeBoList.stream().filter(nodeBo -> ObjectUtil.isEmpty(nodeBo.getCycleParentId())).collect(Collectors.toMap(NodeBo::getId, Function.identity()));
        // 排除掉循环节点的子节点之后，剩下的只有一个，那么就是循环节点本身
        if (idByNodeBoToMap.size() == 1) {
            return idByNodeBoToMap.keySet().iterator().next();
        } else {
            // 入边
            Set<String> targetNodeIdSet = edgeBoList.stream().map(EdgeBo::getTargetNodeId).collect(Collectors.toSet());
            // 出边
            Set<String> sourceNodeIdSet = edgeBoList.stream().map(EdgeBo::getSourceNodeId).collect(Collectors.toSet());
            String rootNodeId = null;
            for (String sourceNodeId : sourceNodeIdSet) {
                NodeBo nodeBo = idByNodeBoToMap.get(sourceNodeId);
                // 跟节点不能有父节点
                if (ObjectUtil.isNotEmpty(nodeBo)
                        && StrUtil.isEmpty(nodeBo.getCycleParentId())
                        && StrUtil.isEmpty(nodeBo.getParentId())
                        // 该节点不能有入边
                        && !targetNodeIdSet.contains(sourceNodeId)
                        // 标记节点不能作为根节点
                        && !NodeEnums.MarkNode.name().equals(nodeBo.getType())) {
                    rootNodeId = sourceNodeId;
                }
            }
            return rootNodeId;
        }
    }

    /**
     * 获取根节点 id
     * 一般是子流程时候用到
     *
     * @param nodeBoList 节点列表
     * @param edgeBoList 边列表
     * @return 根节点 id
     */
    private static String getSubProcessRootNodeId(List<NodeBo> nodeBoList, List<EdgeBo> edgeBoList) {
        Map<String, NodeBo> idByNodeBoToMap = nodeBoList.stream().collect(Collectors.toMap(NodeBo::getId, Function.identity()));
        String rootNodeId = null;
        if (ObjectUtil.isEmpty(edgeBoList) && ObjectUtil.isNotEmpty(nodeBoList) && nodeBoList.size() == 1) {
            // 如果边是空的，节点里面也只有一个节点，则该节点就是根节点
            rootNodeId = nodeBoList.get(0).getId();
        } else if (ObjectUtil.isNotEmpty(edgeBoList)) {
            // 入边
            Set<String> targetNodeIdSet = edgeBoList.stream().map(EdgeBo::getTargetNodeId).collect(Collectors.toSet());
            // 出边
            Set<String> sourceNodeIdSet = edgeBoList.stream().map(EdgeBo::getSourceNodeId).collect(Collectors.toSet());
            for (String sourceNodeId : sourceNodeIdSet) {
                NodeBo nodeBo = idByNodeBoToMap.get(sourceNodeId);
                // 该节点不能有入边
                // 标记节点不能作为根节点
                if (!targetNodeIdSet.contains(sourceNodeId) && !NodeEnums.MarkNode.name().equals(nodeBo.getType())) {
                    rootNodeId = sourceNodeId;
                }
            }
        }
        return rootNodeId;
    }

    /**
     * 获取子流程节点列表
     *
     * @param childNodeIdList 子节点ID列表
     * @param liteFlowContext 逻辑流程上下文
     * @return 子流程节点列表
     */
    private static List<Node> getSubProcessNodeList(List<String> childNodeIdList, LiteFlowContext liteFlowContext) {
        List<Node> subProcessNodeList = new ArrayList<>();
        for (String childNodeId : childNodeIdList) {
            subProcessNodeList.add(liteFlowContext.getIdByNodeToMap().get(childNodeId));
        }
        return subProcessNodeList;
    }

    /**
     * 获取子流程边列表
     *
     * @param childNodeIdList 子节点ID列表
     * @param liteFlowContext 逻辑流程上下文
     * @return 子流程边列表
     */
    private static List<Edge> getSubProcessEdgeList(List<String> childNodeIdList, LiteFlowContext liteFlowContext) {
        List<Edge> subProcessEdgeList = new ArrayList<>();
        for (String childNodeId : childNodeIdList) {
            List<Edge> sourceEdges = liteFlowContext.getSourceIdByEdgeListToMap().get(childNodeId);
            if (ObjectUtil.isNotEmpty(sourceEdges))
                for (Edge sourceEdge : sourceEdges)
                    if (subProcessEdgeList.stream().noneMatch(edge -> sourceEdge.getId().equals(edge.getId())))
                        subProcessEdgeList.add(sourceEdge);
            List<Edge> targetEdges = liteFlowContext.getTargetIdByEdgeListToMap().get(childNodeId);
            if (ObjectUtil.isNotEmpty(targetEdges))
                for (Edge targetEdge : targetEdges)
                    if (subProcessEdgeList.stream().noneMatch(edge -> targetEdge.getId().equals(edge.getId())))
                        subProcessEdgeList.add(targetEdge);
        }
        return subProcessEdgeList;
    }

    /**
     * 从一棵树中提取所有 LinkBo（即新的流程开始节点），包括根节点本身，并从树中剔除这些节点。
     *
     * @param nodeBo 当前树的根节点
     */
    public static List<ProcessBo> buildProcessBoList(NodeBo nodeBo) {
        List<ProcessBo> processBoList = new ArrayList<>();
        if (nodeBo == null) return processBoList;
        NodeBo rootNodeBo = ObjectUtil.cloneByStream(nodeBo);
        // 第一步：把当前 nodeBo 本身构造成最顶层链路（parentLinkStartNodeId 为 null）
        String rootLinkStartId = nodeBo.getId();
        processBoList.add(ProcessBo.buildProcessBo(rootLinkStartId, null, nodeBo, ProcessEnums.MAIN.name()));
        // 第二步：处理它的子节点
        recursionBuildProcessBoList(rootNodeBo, nodeBo, rootLinkStartId, processBoList);
        return removeDuplicateLinks(processBoList);
    }

    /**
     * 内部递归逻辑，用于处理子节点
     *
     * @param rootNodeBo         根节点
     * @param parentNode         当前遍历的父节点
     * @param currentLinkStartId 当前所在链路的起点 ID
     * @param processBoList      收集的 LinkBo 列表
     */
    private static void recursionBuildProcessBoList(NodeBo rootNodeBo, NodeBo parentNode, String currentLinkStartId, List<ProcessBo> processBoList) {
        if (ObjectUtil.isEmpty(parentNode.getChildNodeBoList())) return;
        Iterator<NodeBo> iterator = parentNode.getChildNodeBoList().iterator();
        while (iterator.hasNext()) {
            NodeBo child = iterator.next();
            if (isProcessStart(child)) {
                // 是新流程的起点，构建新的链路
                String newLinkStartId = child.getId();
                if (CategoryEnums.FOR.name().equals(parentNode.getCategory())
                        || CategoryEnums.WHILE.name().equals(parentNode.getCategory())
                        || CategoryEnums.ITERATOR.name().equals(parentNode.getCategory())) {
                    if (ObjectUtil.isEmpty(child.getCycleParentId()))
                        throw new RuntimeException("循环节点的子流程没有设置循环节点的id");
                    // 子流程不应该还保留原来的父节点ID
                    child.setParentId(null);
                    NodeBo cycleNodeBo = TreeUtils.findBrotherNodeBo(rootNodeBo, child.getCycleParentId());
                    if (cycleNodeBo == null) throw new RuntimeException("循环节点的子流程没有获取到插入主流程位置");
                    ProcessBo processBo = ProcessBo.buildProcessBo(newLinkStartId, currentLinkStartId, child, ProcessEnums.CYCLE.name());
                    processBo.setBrotherId(cycleNodeBo.getId());
                    processBoList.add(processBo);
                } else {
                    // 子流程不应该还保留原来的父节点ID
                    child.setParentId(null);
                    ProcessBo processBo = ProcessBo.buildProcessBo(newLinkStartId, currentLinkStartId, child, ProcessEnums.COMMON.name());
                    NodeBo brotherNode = TreeUtils.findBrotherNodeBo(rootNodeBo, newLinkStartId);
                    if (brotherNode == null) throw new RuntimeException("子流程没有获取到插入主流程位置");
                    processBo.setBrotherId(brotherNode.getId());
                    processBoList.add(processBo);
                }
                // 移除该分叉
                iterator.remove();
                // 递归处理这个新的子流程链路
                recursionBuildProcessBoList(rootNodeBo, child, newLinkStartId, processBoList);
            } else {
                // 继续在当前链路下递归
                recursionBuildProcessBoList(rootNodeBo, child, currentLinkStartId, processBoList);
            }
        }
    }

    /**
     * 当前节点是否为流程开始节点
     *
     * @param nodeBo 业务节点
     * @return 是否为流程开始节点
     */
    private static boolean isProcessStart(NodeBo nodeBo) {
        // 当前节点的所有入边
        List<EdgeBo> targetEdgeBoList = nodeBo.getTargetEdgeBoList();
        // 当前节点的所有出边
        List<EdgeBo> sourceEdgeBoList = nodeBo.getSourceEdgeBoList();
        // 当前节点没有入边，只有出边，则该节点是一个流程的开始节点
        if (!CategoryEnums.MARK.name().equals(nodeBo.getCategory())
                && ObjectUtil.isEmpty(targetEdgeBoList)
                && ObjectUtil.isNotEmpty(sourceEdgeBoList)) {
            return true;
        }
        // 当前节点有多个入边，则该节点是一个流程的开始节点
        else if (!CategoryEnums.MARK.name().equals(nodeBo.getCategory())
                && ObjectUtil.isNotEmpty(targetEdgeBoList)
                && targetEdgeBoList.size() > 1) {
            return true;
        }
        return false;
    }

    /**
     * 去除重复链路，并根据规则保留一条链路。
     *
     * @param processBoList 原始链路列表
     * @return 去重后的链路列表
     */
    private static List<ProcessBo> removeDuplicateLinks(List<ProcessBo> processBoList) {
        // 按 linkStartNodeId 分组
        Map<String, List<ProcessBo>> groupedByLinkStartNodeId = processBoList.stream()
                .collect(Collectors.groupingBy(ProcessBo::getId));
        List<ProcessBo> resultList = new ArrayList<>();
        // 遍历每个 linkStartNodeId 的链路
        for (Map.Entry<String, List<ProcessBo>> entry : groupedByLinkStartNodeId.entrySet()) {
            List<ProcessBo> linksWithSameStartId = entry.getValue();
            // 1. 先找出 parentId 为 null 的链路
            Optional<ProcessBo> nullParentLinkBo = linksWithSameStartId.stream()
                    .filter(linkBo -> linkBo.getParentId() == null)
                    .findFirst();
            if (nullParentLinkBo.isPresent()) {
                // 如果找到了 parentLinkStartNodeId 为 null 的链路，直接保留
                resultList.add(nullParentLinkBo.get());
            } else {
                // 如果没有 parentLinkStartNodeId 为 null 的链路，随机选择一个
                resultList.add(linksWithSameStartId.get(0));
            }
        }
        return resultList;
    }

    /**
     * 取所有路径的最长公共前缀（即最近公共祖先）
     *
     * @param root     根节点
     * @param targetId 目标节点ID
     * @return 兄弟节点
     */
    public static NodeBo findBrotherNodeBo(NodeBo root, String targetId) {
        List<List<NodeBo>> paths = findNodeBoPathList(root, targetId);
        if (paths.isEmpty()) return null;
        int index = 0;
        while (true) {
            NodeBo current = null;
            for (List<NodeBo> path : paths) {
                if (index >= path.size()) return index == 0 ? null : paths.get(0).get(index - 1);
                if (current == null) {
                    current = path.get(index);
                } else if (!current.getId().equals(path.get(index).getId())) {
                    return index == 0 ? null : paths.get(0).get(index - 1);
                }
            }
            index++;
        }
    }

    /**
     * 找到对应ID的链路
     *
     * @param root     根节点
     * @param targetId 目标节点ID
     * @return 对应ID的链路
     */
    private static List<List<NodeBo>> findNodeBoPathList(NodeBo root, String targetId) {
        List<List<NodeBo>> result = new ArrayList<>();
        Deque<NodeBo> path = new ArrayDeque<>();
        recursionFindNodeBoPathList(root, targetId, path, result);
        return result;
    }

    /**
     * 递归函数
     *
     * @param current  当前节点
     * @param targetId 目标节点ID
     * @param path     路径
     * @param result   结果
     */
    private static void recursionFindNodeBoPathList(NodeBo current, String targetId, Deque<NodeBo> path, List<List<NodeBo>> result) {
        if (current == null) return;
        path.addLast(current);
        if (targetId.equals(current.getId())) {
            // 保存一条路径
            result.add(new ArrayList<>(path));
            path.removeLast();
            return;
        }
        if (current.getChildNodeBoList() != null) {
            for (NodeBo child : current.getChildNodeBoList()) {
                recursionFindNodeBoPathList(child, targetId, path, result);
            }
        }
        // 回溯
        path.removeLast();
    }

}
